package class16;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

// OJ链接：https://www.lintcode.com/problem/topological-sorting
public class Code03_TopologicalOrderDFS1 {

	// 不要提交这个类
	// 定义有向图节点的数据结构
	public static class DirectedGraphNode {
		public int label;  // 节点的标签值
		public ArrayList<DirectedGraphNode> neighbors;  // 节点的邻居列表（出边连接的节点）

		// 构造函数，初始化节点
		public DirectedGraphNode(int x) {
			label = x;
			neighbors = new ArrayList<DirectedGraphNode>();
		}
	}

	// 提交下面的
	// 定义记录节点及其深度的记录类
	public static class Record {
		public DirectedGraphNode node;  // 图节点
		public int deep;  // 节点的深度（能够到达的最深深度）

		// 构造函数，初始化记录
		public Record(DirectedGraphNode n, int o) {
			node = n;
			deep = o;
		}
	}

	// 自定义比较器，用于按深度降序排序
	public static class MyComparator implements Comparator<Record> {

		// 比较两个记录，按深度降序排列（深度越大的排在前面）
		@Override
		public int compare(Record o1, Record o2) {
			return o2.deep - o1.deep;
		}
	}

	// 拓扑排序主函数，使用DFS实现
	public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
		// 创建一个Map来存储每个节点对应的记录（节点和其深度）
		HashMap<DirectedGraphNode, Record> order = new HashMap<>();
		
		// 对图中每个节点执行DFS，计算其深度
		for (DirectedGraphNode cur : graph) {
			f(cur, order);
		}

		// 将所有记录添加到列表中
		ArrayList<Record> recordArr = new ArrayList<>();
		for (Record r : order.values()) {
			recordArr.add(r);
		}
		
		// 按深度降序排序记录
		recordArr.sort(new MyComparator());
		
		// 构建结果列表
		ArrayList<DirectedGraphNode> ans = new ArrayList<DirectedGraphNode>();
		for (Record r : recordArr) {
			// 按深度从大到小的顺序添加节点到结果中
			ans.add(r.node);
		}
		
		// 返回拓扑排序的结果
		return ans;
	}

	// DFS函数，计算节点能够到达的最大深度
	public static Record f(DirectedGraphNode cur, HashMap<DirectedGraphNode, Record> order) {
		// 如果当前节点已经计算过深度，直接返回缓存的结果
		if (order.containsKey(cur)) {
			return order.get(cur);
		}

		// 初始化后续节点的最大深度为0
		int follow = 0;

		// 遍历当前节点的所有邻居节点
		for (DirectedGraphNode next : cur.neighbors) {
			// 递归计算邻居节点的深度，并更新最大深度
			follow = Math.max(follow, f(next, order).deep);
		}

		// 当前节点的深度为后续节点的最大深度加1
		Record ans = new Record(cur, follow + 1);
		// 将计算结果缓存到order中
		order.put(cur, ans);
		// 返回当前节点的记录
		return ans;
	}

}
